#include <vector>
#include <iostream>
#include <deque>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> queue;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            while (queue.size() > 0 && nums[i] > nums[queue.back()]) {
                queue.pop_back();
            }
            queue.push_back(i);
            if (queue.size() > 0 && queue.front() == i - k) {
                queue.pop_front();
            }
            if (i >= k - 1) {
                ans.push_back(nums[queue.front()]);
            }
        }
        return ans;
    }
};

int main() {
    vector<int> input = {1, 3, -1, -3, 5, 3, 6, 7};
    Solution solution;
    vector<int> output = solution.maxSlidingWindow(input, 3);
    for (int item : output) {
        cout << item << endl;
    }
    return 0;
}